#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution
{
public:
    int minInsertions(string s)
    {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), -1));
        return ms(s, 0, s.size() - 1, dp);
    }

    int ms(string &s, int i, int j, vector<vector<int>> &dp)
    {
        if (i >= j)
            return 0;
        if (dp[i][j] != -1)
            return dp[i][j];
        if (s[i] == s[j])
            return dp[i][j] = ms(s, i + 1, j - 1, dp);
        else
            return dp[i][j] = min(ms(s, i + 1, j, dp), ms(s, i, j - 1, dp)) + 1;
    }
};

int main()
{
    cout << "Code1312" << endl;
    Solution s;
    return 0;
}